|
In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph.〔R. Diestel, ''Graph Theory'', p.8. 3rd Edition, Springer-Verlag, 2005〕 If the graph does not contain any cycles (i.e. it's an acyclic graph), its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free. ==Cages== A cubic graph (all vertices have degree three) of girth that is as small as possible is known as a -cage (or as a (3,)-cage). The Petersen graph is the unique 5-cage (it is the smallest cubic graph of girth 5), the Heawood graph is the unique 6-cage, the McGee graph is the unique 7-cage and the Tutte eight cage is the unique 8-cage.〔. Electronic supplement to the book ''Distance-Regular Graphs'' (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).〕 There may exist multiple cages for a given girth. For instance there are three nonisomorphic 10-cages, each with 70 vertices : the Balaban 10-cage, the Harries graph and the Harries–Wong graph. Image:Petersen1 tiny.svg|The Petersen graph has a girth of 5 Image:Heawood_Graph.svg|The Heawood graph has a girth of 6 Image:McGee graph.svg|The McGee graph has a girth of 7 Image:Tutte eight cage.svg|The Tutte–Coxeter graph (''Tutte eight cage'') has a girth of 8 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Girth (graph theory)」の詳細全文を読む スポンサード リンク
|